package com.singzi.leetcode.N700;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class T0698 {
    public static void main(String[] args) {
        Solution0698 solution0698 = new Solution0698();
        int []nums = {1,1,1,1,2,2,2,2};
        int k = 4;
        System.out.println(solution0698.canPartitionKSubsets(nums, k));
    }
}
class Solution0698 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (k > nums.length) return false;
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        if(sum % k != 0) return false;
        int n = nums.length, target = sum/k;
        Arrays.sort(nums);
        if(nums[n-1] > target) return false;
        int size = 1<<n;
        boolean []dp = new boolean[size];
        int [] sums = new int[size];
        dp[0] = true;
        for (int i = 0; i < size; i++) {
            if(!dp[i]) continue;

            for(int j = 0; j < n;j++){
                if((i & 1<<j) !=0) continue;
                int next = i | 1<<j;
                if (dp[next]) continue;
                if((sums[i] % target + nums[j]) <= target){
                    sums[next] = sums[i] + nums[j];
                    dp[next] = true;
                }else {
                    break;
                }


            }
        }
        return dp[size-1];

    }
}





class Solution06981 {
    List<List<Integer>> list = new ArrayList();
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int n = nums.length;
        if(n < k) return false;
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        if(sum%k != 0) return false;
        int target = sum/k;
        for(int num:nums){
            if(num > target) return false;
        }
        int []visit = new int[n];
        List<Integer> temp = new ArrayList();
//        temp.add(0);
        backTrace(nums, 0, target, temp, visit);
        System.out.println(list.size());
        int[][] set = new int [list.size()][n];
        int index = 0;
        int addIndex = 0;
        boolean flag = false;
        for(List<Integer> s:list){
            co:for(int i = 0;i <= index;i++){
                for(int num:s){
                    if(set[i][num] == 1){
                        continue co;
                    }
                }
                addIndex = i;
                flag = true;
                break;
            }
            if(!flag){
                index++;
                addIndex = index;
            }
            for(int num:s){
                set[addIndex][num] = 1;
            }
            flag = false;
        }
        f:for(int[] st:set){
            System.out.println(Arrays.toString(st));
            for(int num:st){
                if(num == 0) continue f;
            }
            return true;
        }
        return false;
    }
    public void backTrace(int[] nums, int index, int target, List<Integer> temp, int []visit){
        int sum = sumList(temp, nums);
        if(sum == target){
            list.add(new ArrayList<>(temp));
            return;
        }
        for(int i = index;i < nums.length;i++){
            if(sum > target) break;
            temp.add(i);
            backTrace(nums, i+1, target, temp, visit);
            temp.remove(temp.size()-1);
        }
    }
    public int sumList(List<Integer> temp, int[] nums){
        int sum = 0;
        for(int num:temp){
            sum += nums[num];
        }
        return sum;
    }
}
class Solution06982 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (k > nums.length) return false;
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        if(sum % k != 0) return false;
        int n = nums.length, target = sum/k;
        Arrays.sort(nums);
        if(nums[n-1] > target) return false;
        int []buckets = new int[k];
        return backTrack(nums, buckets, nums.length-1, target);
    }
    public boolean backTrack(int[] nums, int []buckets, int index, int target){
        if(index == -1){
            for(int i = 0;i < buckets.length;i++){
                if(buckets[i] != target) return false;
            }
            return true;
        }
        for(int i = 0;i < buckets.length;i++){
            if (buckets[i] + nums[index] > target) {
                continue;
            }
            buckets[i] += nums[index];
            if(backTrack(nums, buckets, index-1, target)) return true;
            buckets[i] -= nums[index];
        }
        return false;

    }
}